
  #include<iostream>  
  //#include"newlist.cpp"
  #include "graph-limits.h"
  #include "../experiment.h"
  #include "../../bn/ClassBN.h"
  #include "../../chi/chisquaredistr.h"
  #include<list>
  #include<vector>
  #define List list
  
  
  
  #define NULL_LINK 0
  // E' il valore nullo dei links.
    

 
  // Dichiarazione di alcune delle classi definite successivamente.
  class Main_node;
  class Multi_individual;
  struct edge
  {int v1, v2;
   float len; 
  };


struct arc{

  float m;
  int number;
  void show(){cout<<endl<<"n: "<<number<<" m:"<<m;};
};

struct n_diff{

  float d;
  int number;
  void show(){cout<<endl<<"n: "<<number<<" m:"<<d;};
};

struct iters{ List<class Main_node>::iterator f, s;
         List<class Link>::iterator l;
  };
  
struct min_score{
  float score;  
  bool *pars;
};

struct mutual_values {
  float avg, dev, max, min;
}; 
  
/*
  ++++++++++++++++++++++++ Classe MULTI_POPULATION +++++++++++++++++++++++++
  *** Definita il: 01/03/04
  Questa classe e' stata definita per contenere degli individui della clas-
  se Multi_individual. In pratica, questa classe si differenzia dalla classe
  base solo per la costruttrice della classe, la quale deve creare per l'ap-
  punto individui della classe Multi_individual. 
  *** Ultima modifica:
  */
  class Multi_population : public Population 
  {
  public:
     Multi_population(int N, Evolution *evo_ptr);
     /* E' la costruttrice della classe. Il parametro N viene passato alla 
        costruttrice della classe base. 
     */
     void breed();
     /* E' la procedura che genera la popolazione di individui della classe 
        dm_Individual.
     */
     void show_data();
  /* Mostra i dati della popolazione.  
  */  
  };
  
  
  /*
  +++++++++++++++++++++++++++ classe  MULTI_EVOLUTION ++++++++++++++++++++++
  *** Definita il: 
  E' la classe derivata da Evolution. Contiene la procedura di start pre il 
  caricamento dei parametri e la generazione della popolazione iniziale del
  tipo Multi_population. 
  *** Ultima modifica: ore 17.00 del 04/04/03
  */

  class Multi_evolution : public Evolution
  {
  public:
    
     void start(int argc, char *argv[]);
     /* E' la procedura per il caricamento dei parametri e la generazione 
        della popolazione di individui della  classe Multi_individual.
     */
     float macro_mut_prob;
     /* E' la probabilita' di applicazione della macromutazione.
     */
     float give_density(){return density;};
     /* Restituisce il valore della densit� delle reti.
     */
     int give_node_num(){return N_nodes;};
     /* Restituisce il numero di variabili delle reti.
     */
     bool give_cpx(){return cpx;};
     /* Restituisce la variabile cpx. 
     */
     bool give_mdl(){return mdl;};
     /* Restituisce la variabile cpx. 
     */
     int give_max_pars(){return max_pars;};
     /* Restituisce la variabile max_pars. 
     */
     int give_max_pars_label(){return max_pars_label;};
     /* Restituisce la variabile max_pars_label. 
     */
     int give_max_bads(){return max_bads;};
     /* Restituisce la variabile max_bads. 
     */
     float give_comb_fact(){return comb_fact;};
     /* Restituisce la variabile cpx. 
     */
     double target_fit;
     float  p_val;
     
     inline int comp_Mtx_diff(graph *dag);
     int give_ordering(int index) {return ordering->get(index);}
     matrx<float> *give_mutualMat(){return mutualMat;}
     float give_threshold(){return threshold;}
     float give_min_thresh(){return min_thresh;}
     float give_max_thresh(){return max_thresh;}
     void build_Mat(query_database db);
     bool ** give_SkelMat(){return SkelMat;}
     int give_max_arcs(){return max_arcs;}

     float give_perm_prob(){return perm_prob;}
     

     bool is_k_cross() {return k_cross;}     
     bool is_perm_mut() {return perm_mut;}
     bool is_mutual_info() {return mutual_info;}
		 bool is_micro_mut() {return micro_mut;}
		 bool is_new_mut() {return !micro_mut;}  

  private:
     bool termination();
     /* Verifica i criteri di terminazione dell'algoritmo per quest'implmen-
        tazione.*/  
     bool extract_more_param(char *line);
     /* e' stata specializzata per la classe per caricare il parametro den-
        sita. */   
     double density;
     /* E' la densit� delle reti iniziali.
     */
     int N_nodes;
     /* E' il numero di variabili del problema.
     */
     int max_pars;
     /* e' il massimo numero di genitori oper un nodo. 
     */
     int max_pars_label;
     /* e' il massimo numero di genitori del nodo label un nodo. 
     */
     int max_bads;
     /* e' il massimo numero di nodi che possono avere max_pars +1 genitori.
     */
     double comb_fact;
     /* e' il fattore moltiplicativo per la complessit� legata al combining.
     */
     float perm_prob;
     /* probabilita di PERMUTAZIONE
     */     
     /** ****************** FLAGS ************************/
     bool cpx;
     /* Vale true sebisogna inserire il termine della comp
        lessit� nel calcolo della fitness. 
     */
     bool mdl;
     /* Vale true se bisogna calcolae lo score con la funz-
        ione di Wong.
     */
     bool k_cross;
     /* Flag per il crossover basato su conoscenza
     */
     bool perm_mut;
     /* Flag per la mutazione che effettua la permutazione
		 */ 
     bool mutual_info;
     /* Flag per  la mutua informazione
		 */
		 bool micro_mut;
		 /* Flag per la micro mutazione 
		 */

     matrx<int> *WongMat;
     /* Punta alla matrice di wong da confrontare. Per la fitness ceh calcola le differenze strutturali tra due matrici.
     */
     matrx<float> *mutualMat;
     /* E' la matrice degli score da usare x l'ordering estimation.
     */
     float threshold, max_thresh, min_thresh;
     /* E' la soglia massima per considerare un arco.
     */
     vectr<float> *scoreVec;
     /* E' il vettore che memorizza gli score singoli dei nodi.
     */
     vectr<int> *ord_weights;
     /* E' il vettore che memorizza i pesi per la stima dell'ordinamento.
     */
     vectr<int> *ordering;
     edge *edge_vec;
     
     bool  **SkelMat;
     /* E' la matrice che memorizza gli archi da considerare
     */
     int max_arcs;
     /* E' il massimo numero di archi quando si considera la mutua informazione.
     */ 
     
  };

  
  /*
  ++++++++++++++++++++++++ Classe Graph ++++++++++++++++++++++++++++++++++++
  *** Definita il: 01/03/04
  Questa classe codifica un generico grafo. E' una classe template e rap
  -presenta il fenotipo per il nostro algoritmo.
  *** Ultima modifica:
  
  class Graph
  {
  public:
     int N_nodes;
     /* E' il numero di nodi contenuto nel grafo.
     
     //val_type1 nodes[MAX_NODES];
     int nodes[MAX_NODES];
     /* E' l'array che contiene i valori dei nodi del grafo.
     
     //val_type2 links[MAX_NODES][MAX_NODES];
     int links[MAX_NODES][MAX_NODES];
     /* E' l'array bidimensionale che contiene i valori dei links del grafo.
     

 // private:
  };
  /*
  ++++++++++++++++++++++++ Classe MULTI_INDIVIDUAL ++++++++++++++++++++++++
  *** Definita il: 01/03/04
  E' un individuo il cui genotipo e' rappresentato da una multilista.
  *** Ultima modifica:
  */
  class Multi_individual : public Individual 
  {
  public:
     Multi_individual();
     /* E' la costruttrice della classe. 
     */
     Multi_individual(Evolution *e_ptr);
     /* E' la seconda costruttrice della classe, passa il puntatore
        alla classe base. 
     */
        
     // Multi_individual(bool cpx, bool mdl, int pars_val, float comb_val);
     /* E' la seconda costruttrice della classe. Serve a settare i valori 
        di cpx e mdl. 
     */
     Multi_individual(graph *Graph_ptr);
     /* E' una seconda procedura costruttrice della classe, serve a costru-
        ire un individuo che contiene il grafo passato come parametro.
     */
     ~Multi_individual();
     /* E' la distruttrice della classe, e' utilizzata per cancellare la
        multi_lista dell'individuo.
     */
     Multi_individual *build_copy();
     /* Costruisce una copia dell'individuo e ne restituisce il puntatore.
     */
     void write_pheno();
     /* Calcola il fenotipo dell' individuo.
     */    
     double comp_fitness();
     /* Calcola la fitness dell'individuo.
     */
     int give_len(){return multi.size();}
     float give_score(int i){return scores[i];}
     /* 
     */
     void kill();
     /* Restituisce alla memoria la superlista utilizzata dall'individuo.
     */
     void copy_graph(graph &g);
     /* Copia la multilista nel struttura dati graph passata come parametro.
     */
     void swap_nodes(int node1, int node2);
     /* Inverte nella multilista i due nodi pasasti come parametri.
     */
     void new_mut();//float perm_mut = 0.5);
     /* E' la micromutazione che implementa anche l'inversione degli archi.
     */
     void new_mut_skel(bool **am);
     /* applica la new mut allo skeleton rappresentato dalla matrice di bool
        passata come parametro
     */
     bool get_best_parents();
     /* migliora la fitness dell'individuo. 
     */
     bool set_parents(int node);
     /* Setta se possibile, i parents del nodo passato come parametro a quelli 
        contenuti in pars.
     */     
   
     iters give_iters(bool **am);
     
     int comp_arcs();
     int comp_arcs(bool **am);
     void put_arc(int &par, int &son);
     matrx<float> *give_mutualMat(){return ((Multi_evolution *)evo_ptr)->give_mutualMat();}
     float give_threshold(){return ((Multi_evolution *)evo_ptr)->give_threshold();}
     bool **give_SkelMat(){return ((Multi_evolution *)evo_ptr)->give_SkelMat();}
     int  give_max_arcs(){return ((Multi_evolution *)evo_ptr)->give_max_arcs();}

	 /*restituisce il vettore delle medie MI dei soli link ordinati secondo la matrice di adiacenza e la matrice di adiacenza*/
	 vectr<float> * giveActualMI(matrx<int> & Adj);
	  /*restituisce il vettore delle medie MI dei soli link ordinati la ML*/
	 vectr<float>  giveActualMI_MLsorted();
	/*restituisce il vettore delle medie MI esplorando le sublists di ogni nodo ordinato secondo la ML*/
	  vectr<float>   giveActualMIofMLelem();
	/*calcola il peso dei nodi nella ML*/
     void computeWeight(int cut=0);
   //private:
     int length;
     /* E' la lunghezza della multilista. In pratica e' il numero di nodi
       contenuto nella multilista dell'individuo.
     */
     float density, threshold;
     bool mdl, cpx;
     int max_pars, max_pars_label, max_bads;
     float comb_fact;
     //list <template<class val_type> class Main_node>::iterator main_ptr;
     // list<class Main_node>::iterator main_ptr;
     List<class Main_node> multi;
     /* E' la multilista dell'individuo.
     */
   //  bool connected_nodes[MAX_NODES];
     /* E' la struttura dati da utilizzare per verificare se il grafo e'
        connesso oppure no.
     */
     void build_multi(int len, float den);
     /* Costruisce in maniera random la multilista dell'individuo. 
         Parametri:
         -- len: numeri di nodi;
         -- den: densit� del grafo;       
     */
     void build_multi2(int len, float den);
     /* Costruisce in maniera random la multilista dell'individuo. 
         Parametri:
         -- len: numeri di nodi;
         -- den: densit� del grafo;       
     */
     void add_arc(int i, int j);
     //void check_multi();
     /* Controlla se la superlista e' completa, in caso contrario effettua
        operazioni necessarie a rfnderla una multilista comtpeta. Tale con-
        trollo viene fatto scandendo la lista principale e chiamando la
        procedura di controllo dei nodi.
     */
     void build_multi(int len, float den, matrx<float> *m);
     /* Costruisce una multilista con ordinamento che si basa sul Liu-Chow tree.
     la matriece m contiene la mutua informazione.
     */
     bool connected();
     /* Restituisce true se la multilista è connessa, false altrimenti.
     */
     void connect(int node);
     /* E' una procedura ricorsiva che utilizzata per la verifica della co-
        nettivita' del grafo.
     */
     bool connected(int node);
     /* Restituisce true se il nodo passato come parametro (si passa la sua
        posizione all'interno della main list) e' connesso al resto del gr-
        afo, false altrimenti.
     */
     void show(ostream *out_stream);
     /* Visualizza gli attributi dell'individuo.
     */
     void show_graph(ostream *out_stream);
     /* Sullo stream specificato dal parametro stampa il grafo codificato dalla
        multilista nel formato AISEE.  
     */    
     float *scores;
     /* memorizza il vettore degli score dei nodi.
     */
     
     
  //private:
  friend class Multi_population; 
  };

  
  /*
  ++++++++++++++++++++++++ Classe Main_node ++++++++++++++++++++++++++++++++++++
  *** Definita il: 01/03/04
  Rappresenta un nodo della multilista. E' una classe template, in quanto
  nei nodi puo' essere contenuta informazione di tipo diverso. La variabile
  first e' il puntatore al primo elemento della sottolista del nodo rappre-
  sentato. La vcariabile val contiene il valore contenuto nel nodo.
  *** Ultima modifica:
  */
  //template <class val_type> class Main_node
  class Main_node
  {
  public:
     Main_node();
     /* E' la procedura costruttrice della classe.
     */
     Main_node(int value, float den, int position, int sub_len);
     /* E' la seconda costruttrice della classe. I parametri sono:
        -- value: valore da assegnaer al nodo.
        -- den: densita' del grafo.
        -- position: posizione del nodo nella multilista.
	-- sub_len: lunghezza della sottlosita da costruire.
     */
     
     ~Main_node();
     /* Cancella la sottolista del nodo.
     */
     long int val;
     /* E' il valore contenuto nel nodo.
     */
     int pos;
     /* E' la posizione del nodo all'interno della lista principale. PARTE
        DAL VALORE UNO!
     */   
	 
	 float weight; // rappresenta il peso del nodo inteso come somma della MI archi entrani ed uscenti 

     void swap_arcs(int arc1, int arc2);
     /* Inverte gli attributi dei due archi passsati come parametri. 
     */
     void add_arcs(float den);
     /* Aggiunge archi nodo secondo la probablit� specificata da den.
     */
     int set_arc_value(int arc, int val);
     /*  modifica il valore dell'arco passato come primo parametro con il 
         valore passato come secondo parametro.  La funzione restituisce 
	 il vecchio valore contenuto nell'arco. 
     */ 
     void add_arcs(float den, bool **am, List<class Main_node>::iterator next_iter);
     /* Aggiunge gla archi al nodo, secondo la matrice degli score passata
        come parametro. Vengono esclusi tutti gli archo al di sotto della 
	soglia. 
     */
//  private:
     List<class Link> sub;
     /* E' la sottolista del nodo.
     */     
     int give_val();
     /* E' la procedura che restituisce un valore generato random.
     */
     int give_value(){return val;};
     /* Ritorna il valore del nodo .
     */
     void check_sub(int right_len);
     /* Verifica la lunghezza della sottolista e, se necessario, esegue le 
        azioni appropriate. Il parametro right_len specifica la lunghezza 
	    giusta della sottolista del nodo.
     */
      void mutation(float prob);
     /* Serve ad applicare la mutazione al nodo principale e a tutti gli 
        elementi della sua sottolista. 
     */
     void mutation(float prob, bool **am, List<class Main_node>::iterator next_iter);
     /* Applica la mutazione secondo la matrice passata come parametro.
     */ 
     void mutation(float prob, List<class Main_node>  &multi, 
                   List<class Main_node>::iterator this_iter);
     /* Applica la nuova mutazione che effettua anche la permutazione dei nodi.     
     */
     bool show_node(ostream *out_stream, int index);
     /* Mostra i valori contenuti nel nodo e la relativa sottolista. 
     */
  };

 

  /*
  ++++++++++++++++++++++++ Classe LINK ++++++++++++++++++++++++++++++++++++
  *** Definita il: 01/03/04
  Gli oggetti di questa classe rappresentano gli elementi delle sottoliste
  Questa e' una classe template. In quanto gli elementi delle sottoliste
  possono contenere un tipo di informazione variabile.
  *** Ultima modifica:
  */
  //template <class val_type> class Link
  class Link
  {
  public:
     Link();
     /* E' la procedura costruttrice della classe.
     */
     Link(int position);
     /* E' una seconda procedura costruttrice della classe. Il parametro po-
        sition indica la posizione del link nella sottolista. 
     */
     Link(int position, int value);
     /* E' una terza procedura costruttrice della classe. Rispetto alla pre-
        cedente, il parametro val inidica il valore che deve essere assunto 
	link. 
     */
     ~Link();
     /* E' la dstruttrice della classe e' vuota.
     */
     //val_type val;
     long int val;
     /* E' il valore contenuto nel link.
     */
     int pos;
     /* E' la posizione del link all'interno della sottolista. PARTE DAL
        VALORE UNO!
     */
         
//  private:
     //val_type give_val();
     int give_val();
     /* Genera in maniera random un valore del tipo val_type.
     */
     int give_value(){return val;};
     /* Ritorna il valore del nodo .
     */
  };
   
   
  /*
  ++++++++++++++++++++++++ Classe MULTI_CROSSOVER ++++++++++++++++++++++++++
  *** Definita il: 01/03/04
  Gli oggetti di questa classe applicano l'operatore di crossover alle mul-
  tiliste degli individui.    
  *** Ultima modifica:
  */
  class Multi_crossover : public Crossover
  {
	private:
		bool pHybridFlag;
   public: 
	  
     Multi_crossover();
     /* E' la prima procedura costruttrice della classe, e' vuota.
     */
     Multi_crossover(Multi_evolution *evo_ptr);
     /* E' la seconda costruttrice della classe. Il primo parametro rappresenta la
        probabilita' di applicazione dell'operatore. Il secondo, l'uso della conoscenza.
     */
     void apply(Individual *input_ptr1, Individual *input_ptr2,
                Individual* &output_ptr1, Individual* &output_ptr2);
      /* Applica la crossover ai due individui passati come primi due para-
         metri. Gli ultimi due puntatori puntano agli individui modificati 
	 generati dalla procedura.
      */
      void apply(Individual *input_ptr1, Individual *input_ptr2,
                Individual* &output_ptr);
      /* Applica il merge e genera un unico individuo.
      */
      
     void cross(List<class Main_node> &multi_1,
                List<class Main_node> &multi_2);
     /* Applica il crossover alle due liste passate come parametri.
     */ 	

	
     void repair(List<class Main_node> &multi_1, 
                 List<class Main_node> &multi_2, int cut);
     /* Ripara le multiliste passate in ingresso dopo il crossover. Il terzo
        parametro e' il punto di taglio. 
     */   

//ALE:
	  bool getHybridFlag(){return pHybridFlag;};
	   void Hybridize(){pHybridFlag=true;};
	   void UnHybridize(){pHybridFlag=false;};
	   /*int findCutPoint(List<class Main_node> &multi_1,
                List<class Main_node> &multi_2 , vectr<float> * scV1, vectr<float> * scV2);*/
	
	  int findCutPoint(Individual *input_ptr1, Individual *input_ptr2);
	  void crossM(Individual *output_ptr1, Individual *output_ptr2);
     /* Ripara le multiliste passate in ingresso dopo il crossover. Il terzo
        parametro e' il punto di taglio. 
     */ 
     

  };

  /*
  ++++++++++++++++++++++++ Classe MULTI_MUTATION +++++++++++++++++++++++++++
  *** Definita il: 01/03/04
  Gli oggetti di questa classe applicano l'operatore di mutazione alle mul-
  tiliste degli individui.    
  *** Ultima modifica:
  */
  class Multi_mutation : public Mutation 
  {
    public: 
     Multi_mutation();
     /* E' la prima procedura costruttrice della classe, e' vuota.
     */
     Multi_mutation(Multi_evolution* evo_ptr);
     /* E' la seconda costruttrice della classe. Il primo e il secondo para-
     metro rappresentano rispettivamente le probabilita' di micro di macro
     mutazione. */
     void apply(Individual *input_ptr, Individual* &output_ptr);
     /* Questa versione di apply viene definita per motivi di ereditarieta',
        in quanto questa funzione e' derivata dalla classe base Mutation.
     */
     void apply(Individual* &input_ptr);
     /* Questa funzione viene definita per gli stessi motivi della preceden-
        te. 
     */
     void mutate(Individual* input_ptr);
     /* Applica la mutazione 
		*/
     void micro_mut(List<class Main_node> &multi);
     /* Applica la micromutazione alla multilista passata come parametro. 
     */
     
     //void macro_mut(List<class Main_node> &multi);
     /* Applica la macromutazione alla multilista passata come parametro.
     */    
     void per_mut(List<class Main_node> &multi);
     /* Permuta la main list della multilista passata come parametro.
     */
     void per_mut2(List<class Main_node> &multi);
     /* Permuta la main list della multilista passata come parametro.
     */
     void per_ins(List<class Main_node> &multi);
     float perm_prob;
     /* E' la probabilita' di applicazione della permutazione.	 
     */
   private:
 		 bool **SkelMat;
		 /* Matrice che rappresenta lo skeleton generato dalla mutua informazione
		*/
		 bool perm_mut;
     /* Flag per la mutazione che effettua la permutazione
		 */ 
     bool mutual_info;
     /* Flag per  la mutua informazione
		 */
		 bool micro;
		 /* Flag per la micro mutazione 
		 */
     
  };
  
  


